package com.mid;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * Created by Lxk on 2020/2/1.
 */
public class Solution77 {

    private Stack<Integer> stack = new Stack<>();

    private List<List<Integer>> res = new ArrayList<>();

    private void findCombine(int curNum, int limit, int numLimit) {
        if (curNum > limit || stack.size() == numLimit) {
            if (stack.size() == numLimit) {
                List<Integer> curList = new ArrayList<>();
                for (Integer val : stack) {
                    curList.add(val);
                }
                res.add(curList);
            }
            return;
        }
        //添加数据curNum
        if (stack.size() < numLimit) {
            stack.push(curNum);
            findCombine(curNum + 1, limit, numLimit);
            stack.pop();
        }
        //不添加数据curNum
        findCombine(curNum + 1, limit, numLimit);
    }

    public List<List<Integer>> combine(int n, int k) {
        res.clear();
        findCombine(1, n, k);
        return res;
    }

    public static void main(String[] args) {
        Solution77 solution77 = new Solution77();
        System.out.println(solution77.combine(4, 2));
    }
}
